package core;

public class PriorityQueue
{
    private static int CAPACITY_DEFAULT=26*2;
    private Vertex[] array;
    private int currentSize;
    PriorityQueue()
    {
        array=new Vertex[CAPACITY_DEFAULT];
    }
    public PriorityQueue(Vertex[] vertexes)
    {
        currentSize=vertexes.length;
        array=new Vertex[currentSize*2+1];

        int i=1;
        for (Vertex vertex:vertexes)
            array[i++]=vertex;

        buildQueue();
    }
    void enqueue(Vertex newVertex)
    {
        if (currentSize==array.length-1)
            enlargeArray(array.length*2+1);

        int hole=++currentSize;
        for (array[0]=newVertex;newVertex.compareTo(array[hole/2])<0;hole/=2)
        {
            array[hole]=array[hole/2];
        }
        array[hole]=newVertex;
    }
    public Vertex deleteMin()
    {
        if (isEmpty())
        {
            System.out.println("EmptyException");
            return null;
        }
        else
        {
            Vertex min=getPeek();
            array[1]=array[currentSize--];
            percolateDown(1);

            return min;
        }
    }
    private void percolateDown(int hole)
    {
        int child;
        Vertex tmp=array[hole];
        for (;hole*2<=currentSize;hole=child)
        {
            child=hole*2;
            if (child!=currentSize&&array[child+1].compareTo(array[child])<0)
                child++;
            if (array[child].compareTo(tmp)<0)
            {
                array[hole]=array[child];
            }
            else
                break;
        }
        array[hole]=tmp;
    }
    Vertex getPeek()
    {
        if (isEmpty())
        {
            System.out.println("EmptyException");
            return null;
        }
        return array[1];
    }
    int getCurrentSize()
    {
        return currentSize;
    }
    private boolean isEmpty()
    {
        return currentSize==0;
    }
    private void enlargeArray(int capacity)
    {
        Vertex []enArray=new Vertex[capacity];
        for (int i=0;i<array.length;i++)
        {
            enArray[i]=array[i];
        }
        array=enArray;
    }

    private void buildQueue()
    {
        for (int i=currentSize/2;i>0;i--)
        {
            percolateDown(i);
        }
    }
    public void pre_order(int i)
    {
        if (i>currentSize)
            return;
        //System.out.println(array[i].freq);
        pre_order(2*i);
        pre_order(2*i+1);
    }
}
